package demo2;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-09-03
 * Time: 21:39
 */

import java.util.Arrays;

/**
 * 冒泡排序思想 : 将给定的数据从相邻两两进行比较, 将较大的和较小的交换, 最终完成排序
 */
public class BubbleSort {

    /**
     * TODO : 时间复杂度分析, 每一趟相邻比较, 交换一个最大的元素到最后 O(N^2)
     *        空间复杂度分析, 没有额外开辟新的空间 O(1)
     *        稳定性分析, 是一种稳定的排序
     */
    public static void bubbleSort(int[] array) {
        // 最后一次不在需要排
        for (int i = 0; i < array.length - 1; i++) {
            // 防止本身就是升序数组, 采用标志位进行处理
            boolean flag = true;
            // 每一趟过后, 都会有一个数在数组最后向前变得有序排列, 因此这些数不在需要参加排序
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flag = false;
                }
            }
            // 表明已经有序了, 不在需要排序了
            if (flag) {
                break;
            }
        }
    }

    private static void swap(int[] array, int j, int i) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        BubbleSort.bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
}
